#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes);

int main()
{
	return 0;
}

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes)
{
	//*returnSize = (numsSize + 1) * numsSize / 2 + 1;
	*returnSize = 1 << numsSize;
	*returnColumnSizes = calloc(*returnSize, sizeof(int));

	int** res = calloc(*returnSize, sizeof(void*));
	int aux[numsSize]; memset(aux, 0, sizeof(aux));
	for (int bitmap = 0, len = *returnSize; bitmap < len; bitmap++) {
		int size = 0;
		for (int i = 0; i < numsSize; i++)
			if (bitmap & (1 << i)) aux[size++] = nums[i];

		int* layer = malloc(size * sizeof(int));
		memcpy(layer, aux, size * sizeof(int));
		(*returnColumnSizes)[bitmap] = size;
		res[bitmap] = layer;
	}

	return res;
}
